#pragma once

#include <vector>
#include <algorithm>
#include <functional>

#include "compare.h"
#include "util.h"

using namespace std;

template<typename T>
class Merge
{
  vector<T> _v;

  function<bool(const T&,const T&)> _compare;

  vector<T> _merge(const vector<T> &v1, const vector<T> &v2)
  {
    vector<T> r;

    // aloca espaço para o array dos dois mesclados. Na minha máquina melhorou em ~20% a performance :-)
    r.reserve(v1.size() + v2.size());

    int i1 = 0, i2 = 0;

    while (i1 < v1.size() && i2 < v2.size()) {
      r.push_back(!_compare(v1[i1],v2[i2]) ? v1[i1++] : v2[i2++]);
    }
    
    // i1 chegou ao final, sobrou só de v2
    if (i1 == v1.size()) {
      r.insert(r.end(),v2.begin() + i2,v2.end());      
    } else { // i2 == v2.size()
      r.insert(r.end(),v1.begin() + i1,v1.end());      
    }

    return r;
  }

  vector<T> _sort(const vector<T> &v)
  {
    if (v.size() < 2) {
      return v;
    }

    int m = v.size() / 2;

    // ordena um vetor que vai do índice 0 até m
    vector<T> l = _sort({v.begin(), v.begin() + m});

    // ordena um vetor que vai do índice m+1 até v.size() - 1
    vector<T> r = _sort({v.begin() + m, v.end()});

    return _merge(l,r);
  }

public:

  Merge(const vector<T> &v, const function<bool(const T&, const T&)> &c = CompareMax<T>()):
  _v(v),
  _compare(c)
  {
  }

  vector<T> sort()
  {
    return _sort(_v);
  }
};
